package cn.chen.算法.十算法;

// KMP算法
public class KMPAlgorithm {

    public static void main(String[] args) {

        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";

        int index = kmpSearch(str1, str2, kmpNext(str2));
        System.out.println(index);
    }

    //  查找索引
    public static int kmpSearch(String str1, String str2, int[] kmpNext) {

        for (int i = 0, j = 0; i < str1.length(); i++) {

            // kmp 算法的核心
            while (j > 0 && str1.charAt(i) != str2.charAt(j))
                j = kmpNext[j - 1];

            if (str1.charAt(i) == str2.charAt(j))
                j++;

            if (j == str2.length())
                return i - j + 1;       // j 比 i先加1
        }
        return -1;
    }

    // 获取一个字符串（（子串）的部分匹配值
    public static int[] kmpNext(String str) {

        // 创建一个数组，保存部分匹配值
        int[] kmpNext = new int[str.length()];

        kmpNext[0] = 0;   // 字符串长度为1，没有前缀没有后缀，所以重复元素没有。所以为0
        for (int i = 1, j = 0; i < str.length(); i++) {    // j就是记录部分匹配值的

            // 当str.charAt(i)!=str.charAt(j)  我们需要从kmpNext[j-1]获取j
            // 直到str.charAt(i)==str.charAt(j) 才退出
            // 这是kmp算法的核心点
            while (j > 0 && str.charAt(i) != str.charAt(j))
                j = kmpNext[j - 1];

            // 满足这个条件，部分匹配值就要+1。为什么？  这里就是找到j这个元素在该字符串中存在 j就往后走一步
            if (str.charAt(i) == str.charAt(j))
                j++;

            kmpNext[i] = j;
        }
        return kmpNext;
    }
}
